//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// mat[i][j] is either 0 or 1. 
// mat 中至少有一个 0 
// 
//
// 
//
// 
// 注意：本题与主站 542 题相同：https://leetcode-cn.com/problems/01-matrix/ 
//
// Related Topics 广度优先搜索 数组 动态规划 矩阵 👍 33 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_107 {

    /**
     * DFS
     */
    int min = 0;
    int[][] visited;

    public int[][] updateMatrix1(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] arr = new int[m][n];
        visited = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    min = Integer.MAX_VALUE;
                    traversal(i, j, mat, 0);
                    arr[i][j] = min;
                }
            }
        }
        return arr;
    }

    public void traversal(int i, int j, int[][] mat, int count) {
        if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length || visited[i][j] == 1) {
            return;
        }
        // 剪枝，必须剪枝才能通过，否则超时
        if (count > min) return;
        if (mat[i][j] == 0) {
            min = Math.min(min, count);
            return;
        }
        visited[i][j] = 1;
        traversal(i + 1, j, mat, count + 1);  //这里必须count+1,不能count++,也不能++count,
        traversal(i - 1, j, mat, count + 1);
        traversal(i, j + 1, mat, count + 1);
        traversal(i, j - 1, mat, count + 1);
        visited[i][j] = 0;
    }

    /**
     * bfs
     *
     * @param mat
     * @return
     */
    public int[][] updateMatrix2(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        int[] x = {0, 1, -1, 0};
        int[] y = {1, 0, 0, -1};
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = arr[0] + x[i];
                int ny = arr[1] + y[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) {
                    continue;
                }
                queue.offer(new int[]{nx, ny});
                dist[nx][ny] = dist[arr[0]][arr[1]] + 1;
                visited[nx][ny] = true;
            }
        }
        return dist;
    }


    /**
     * 动态规划
     *
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            //不能为Integer.MAX_VALUE，否则1+Integer.MAX_VALUE就会变成最小负数
            Arrays.fill(dist[i], Integer.MAX_VALUE/2);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    if (i - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], 1 + dist[i - 1][j]);
                    }
                    if (j - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], 1 + dist[i][j - 1]);
                    }
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (mat[i][j] == 1) {
                    if (i + 1 < m) {
                        dist[i][j] = Math.min(dist[i][j], 1 + dist[i + 1][j]);
                    }
                    if (j + 1 < n) {
                        dist[i][j] = Math.min(dist[i][j], 1 + dist[i][j + 1]);
                    }
                }
            }
        }
        return dist;
    }


//    public static void main(String[] args) {
//        int[][] ints = new Solution().updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}});
//    }
}
//leetcode submit region end(Prohibit modification and deletion)
